package club.babyf.nativeai.demo.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * GenerateParenthesis.
 *
 * @author zhanglei.
 * @date 2025/4/8 22:01.
 * @description TODO.
 */
public class _1_GenerateParenthesis {

    List<String> res = new ArrayList<>();

    StringBuilder path = new StringBuilder();

    public List<String> generateParenthesis(int n) {
        backTracking(0, 0, n);
        return res;
    }

    private void backTracking(int left, int right, int n) {
        if (left > n || right > n || left < right) {
            return;
        }

        if (path.length() == 2 * n) {
            res.add(path.toString());
        }

        path.append("(");
        backTracking(left + 1, right, n);
        path.deleteCharAt(path.length() - 1);

        path.append(")");
        backTracking(left, right + 1, n);
        path.deleteCharAt(path.length() - 1);
    }

    public static void main(String[] args) {
        _1_GenerateParenthesis generateParenthesis = new _1_GenerateParenthesis();
        List<String> strings = generateParenthesis.generateParenthesis(3);
        System.out.println(strings);
    }

}
